package main

import (
	"fmt"
	"math"
	"sort"
	"time"
)

// O(log (m+n) )
func main() {
	begin := time.Now()
	fmt.Println(BinarySearch2([]int{3, 4, 5, 6}, []int{1, 2}))
	end := time.Now()
	fmt.Println(end.Sub(begin))
}

// O((m+n)log(m+n)) 快速排序
func common0(nums1 []int, nums2 []int) float64 {
	num := append(nums1, nums2...)
	sort.Ints(num)
	if len(num)%2 == 0 {
		return (float64(num[len(num)/2]) + float64(num[len(num)/2-1])) / 2
	} else {
		return float64(num[len(num)/2])
	}
}

// O(m+n) 归并
func common1(nums1 []int, nums2 []int) float64 {
	if len(nums1) == 0 {
		// a trick
		return (float64(nums2[len(nums2)/2]) + float64(nums2[(len(nums2)-1)/2])) / 2
	}
	if len(nums2) == 0 {
		return (float64(nums1[len(nums1)/2]) + float64(nums1[(len(nums1)-1)/2])) / 2
	}
	p1, p2 := 0, 0
	sum := len(nums1) + len(nums2)
	i1, i2 := sum/2, (sum-1)/2
	c := make([]int, i1+1)
LOOP:
	for i := 0; i <= i1; i++ { // 稍微剪枝了一下
		if p1 == len(nums1) {
			for j := p2; j <= len(nums2); j++ {
				c[i] = nums2[j]
				if i == i1 {
					break LOOP
				}
				i++
			}
		}
		if p2 == len(nums2) {
			for j := p1; j <= len(nums1); j++ {
				c[i] = nums1[j]
				if i == i1 {
					break LOOP
				}
				i++
			}
			break
		}
		if nums1[p1] < nums2[p2] {
			c[i] = nums1[p1]
			p1++
		} else {
			c[i] = nums2[p2]
			p2++
		}
	}
	return (float64(c[i1]) + float64(c[i2])) / 2
}

const IntMax = math.MaxInt
const IntMin = math.MinInt

func BinarySearch2(nums1 []int, nums2 []int) float64 {
	if len(nums1) == 0 {
		// a trick
		return (float64(nums2[len(nums2)/2]) + float64(nums2[(len(nums2)-1)/2])) / 2
	}
	if len(nums2) == 0 {
		return (float64(nums1[len(nums1)/2]) + float64(nums1[(len(nums1)-1)/2])) / 2
	}
	l, r := 0, len(nums1)
	nl := (len(nums1) + len(nums2) + 1) >> 1
	// 防止边界问题...
	nums1 = append(append([]int{IntMin}, nums1...), IntMax)
	nums2 = append(append([]int{IntMin}, nums2...), IntMax)
	cut := 0
LOOP:
	for l <= r {
		mid := l + ((r - l) >> 1)
		// 边界问题...
		if mid > nl {
			mid = nl
		}
		if nl-mid > len(nums2)-2 {
			mid = nl - len(nums2) + 2
		}
		next := nl - mid
		switch cmp(nums1[mid], nums1[mid+1], nums2[next], nums2[next+1]) {
		case 1:
			r = mid - 1
		case -1:
			l = mid + 1
		case 0:
			cut = mid
			break LOOP
		}
	}
	lm := nums1[cut]
	if nums2[nl-cut] > lm {
		lm = nums2[nl-cut]
	}
	rm := nums1[cut+1]
	if nums2[nl-cut+1] < rm {
		rm = nums2[nl-cut+1]
	}
	if (len(nums1)+len(nums2))%2 == 1 {
		return float64(lm)
	} else {
		return float64(lm+rm) / 2.0
	}
}

// cmp
// [a | b]
// [c | d]
func cmp(a, b, c, d int) int {
	if a <= d && c <= b {
		return 0
	}
	if a > d {
		return 1 // << |
	}
	return -1 // >> |
}
